package code.classic150on2025;

import utils.TreeNode;

import java.util.*;

public class BinTree {
    // 105. 从前序与中序遍历序列构造二叉树
    public TreeNode buildTree_105(int[] preorder, int[] inorder) {
        Map<Integer, Integer> map = new HashMap<>(); // key是节点元素数字，value是他在inorder中的位置
        for (int i = 0; i < inorder.length; i++)
            map.put(inorder[i], i);
        return build105(map, preorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode build105(Map<Integer, Integer> map, int[] preorder, int pleft, int pright, int ileft, int iright) {
        if (pleft > pright || ileft > iright)
            return null;
        int midNum = preorder[pleft];
        int inMidPos = map.get(midNum);
        // ileft~inMidPos-1 inMidPos inMidPos+1~iright
        int ileftCount = inMidPos - ileft;
        TreeNode node = new TreeNode(midNum);
        node.left = build105(map, preorder, pleft + 1, pleft + ileftCount, ileft, inMidPos - 1);
        node.right = build105(map, preorder, pleft + ileftCount + 1, pright, inMidPos + 1, iright);
        return node;
    }

    // 106. 从中序与后序遍历序列构造二叉树
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        Map<Integer, Integer> map = new HashMap<>(); // key是节点元素数字，value是他在inorder中的位置
        for (int i = 0; i < inorder.length; i++)
            map.put(inorder[i], i);
        return build106(map, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }

    private TreeNode build106(Map<Integer, Integer> map, int[] postorder, int ileft, int iright, int pleft, int pright) {
        if (ileft > iright || pleft > pright)
            return null;
        int midNum = postorder[pright];
        int inMidPos = map.get(midNum);
        int ileftCount = inMidPos - ileft;
        TreeNode node = new TreeNode(midNum);
        node.left = build106(map, postorder, ileft, inMidPos - 1, pleft, pleft + ileftCount - 1);
        node.right = build106(map, postorder, inMidPos + 1, iright, pleft + ileftCount, pright - 1);
        return node;
    }

    // 117. 填充每个节点的下一个右侧节点指针 II
    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;
        public Node() {}
        public Node(int _val) {
            val = _val;
        }
        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

    public Node connect(Node root) {
        if (root == null) return null;
        Deque<Node> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int nowNum = queue.size();
            Node pre = null;
            for (int i = 0; i < nowNum; i++) {
                Node now = queue.poll();
                if (i != 0) pre.next = now;
                if (now.left != null)
                    queue.offer(now.left);
                if (now.right != null)
                    queue.offer(now.right);
                pre = now;
            }
        }
        return root;
    }

    // 114. 二叉树展开为链表
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;
        return sum114(root, 0);
    }

    private int sum114(TreeNode root, int val) {
        int newVal = val * 10 + root.val;
        if (root.right == null && root.left == null)
            return newVal;
        int sum = 0;
        if (root.left != null)
            sum += sum114(root.left, newVal);
        if (root.right != null)
            sum += sum114(root.right, newVal);
        return sum;
    }

    // 124. 二叉树中的最大路径和
    int maxAns = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxPath124(root);
        return maxAns;
    }

    private int maxPath124(TreeNode root) {
        if (root == null)
            return 0;
        int left = maxPath124(root.left);
        int right = maxPath124(root.right);
        // 更新: 1.左中右 2.左中 3.中右 4.中
        maxAns = Math.max(maxAns, Math.max(Math.max(root.val, left + right + root.val), Math.max(left + root.val, right + root.val)));
        // 返回: 1.左中 2.中 3.中右
        return Math.max(root.val, Math.max(root.val + left, root.val + right));
    }

    // 173. 二叉搜索树迭代器
    class BSTIterator {
        TreeNode node;
        Deque<TreeNode> stack;

        public BSTIterator(TreeNode root) {
            stack = new ArrayDeque<>();
            node = root;
        }

        public int next() {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            TreeNode next = node;
            node = node.right;
            return next.val;
        }

        public boolean hasNext() {
            return !stack.isEmpty() || node != null;
        }
    }

    // 236. 二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        if (root == p || root == q)
            return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null)
            return right;
        if (right == null)
            return left;
        return root;
    }
}
